% ====================================================================
% 159.402 	Programming Languages Project 2
% 			Dynamic Maze
% ====================================================================
%	This project attempts to solve a dynamically changing maze using
%	Bratko's best first search algorithm.

% --------------------------------------------------------------------
% Maze Model
% --------------------------------------------------------------------

% node(N, ID).
%	Dynamic nodes
%	N is node name
%	ID is random function ID
node(a,0).
node(b,1).
node(c,2).
node(d,3).
node(e,4).
node(f,5).
node(g,6).
node(h,7).
node(i,8).
node(j,9).
node(k,10).
node(l,11).
node(m,12).
node(n,13).
node(o,14).
node(p,15).
node(q,16).
node(r,17).
node(s,18).
node(t,19).
node(u,20).
node(v,21).
node(w,22).
node(x,23).
node(y,24).
node(z,25).
node(aa,26).
node(ab,27).
node(ac,28).
node(ad,29).
node(ae,30).
node(af,31).
node(ag,32).
node(ah,33).
node(ai,34).
node(aj,35).
node(ak,36).
node(al,37).
node(am,38).
node(an,39).
node(ao,40).
node(ap,41).
node(aq,42).
node(ar,43).
node(as,44).
node(at,45).
node(au,46).
node(av,47).
node(aw,48).
node(ax,49).
node(ay,50).
node(az,51).
node(ba,52).
node(bb,53).
node(bc,54).
node(bd,55).
node(be,56).
node(bf,57).
node(bg,58).
node(bh,59).
node(bi,60).
node(bj,61).
node(bk,62).
node(bl,63).
node(bm,64).
node(bn,65).
node(bo,66).
node(bp,67).
node(bq,68).
node(br,69).
node(bs,70).
node(bt,71).
node(bu,72).
node(bv,73).
node(bw,74).
node(bx,75).
node(by,76).
node(bz,77).
node(ca,78).
node(cb,79).
node(cc,80).
node(cd,81).
node(ce,82).
node(cf,83).
node(cg,84).
node(ch,85).
node(ci,86).
node(cj,87).
node(ck,88).
node(cl,89).
node(cm,90).
node(cn,91).
node(co,92).
node(cp,93).
node(cq,94).
node(cr,95).
node(cs,96).
node(ct,97).
node(cu,98).
node(cv,99).
node(cw,100).
node(cx,101).
node(cy,102).
node(cz,103).
node(da,104).
node(db,105).
node(dc,106).
node(dd,107).
node(de,108).
node(df,109).
node(dg,110).
node(dh,111).
node(di,112).
node(dj,113).
node(dk,114).
node(dl,115).
node(dm,116).
node(dn,117).
node(do,118).
node(dp,119).
node(dq,120).
node(dr,121).
node(ds,122).
node(dt,123).
node(du,124).
node(dv,125).
node(dw,126).
node(dx,127).
node(dy,128).
node(dz,129).
node(ea,130).
node(eb,131).
node(ec,132).
node(ed,133).
node(ee,134).
node(ef,135).
node(eg,136).
node(eh,137).
node(ei,138).
node(ej,139).
node(ek,140).
node(el,141).
node(em,142).
node(en,143).
node(eo,144).
node(ep,145).
node(eq,146).
node(er,147).
node(es,148).
node(et,149).
node(eu,150).
node(ev,151).
node(ew,152).
node(ex,153).
node(ey,154).
node(ez,155).
node(fa,156).
node(fb,157).
node(fc,158).
node(fd,159).
node(fe,160).
node(ff,161).
node(fg,162).
node(fh,163).
node(fi,164).
node(fj,165).
node(fk,166).
node(fl,167).
node(fm,168).
node(fn,169).
node(fo,170).
node(fp,171).
node(fq,172).
node(fr,173).
node(fs,174).
node(ft,175).
node(fu,176).
node(fv,177).
node(fw,178).
node(fx,179).
node(fy,180).
node(fz,181).
node(ga,182).
node(gb,183).
node(gc,184).
node(gd,185).
node(ge,186).
node(gf,187).
node(gg,188).
node(gh,189).
node(gi,190).
node(gj,191).
node(gk,192).
node(gl,193).
node(gm,194).
node(gn,195).
node(go,196).
node(gp,197).
node(gq,198).
node(exit,199).

% node(N).
%	Static nodes
%	N is the node name
node(entrance).
node(static01).
node(static02).
node(static03).
node(static04).
node(static05).
node(static06).
node(static07).
node(static08).
node(static09).
node(static10).
node(static11).
node(static12).

% decide#(Number,Node)
%	decides connected nodes. 
%	  e.g. decide01 decides nodes connected to static01
decide01(0, static02).
decide01(1, static03).
decide01(2, static04).
decide02(0, static05).
decide02(1, static06).
decide07(0, static11).
decide07(1, static12).

% connected(N1,N2).
%	Connected static nodes
%	N1 must be a node
%	N2 must be a node
connected(entrance, static01).
% connected(static01, static02).
% connected(static01, static03).
% connected(static01, static04).
% connected(static02, static05).
% connected(static02, static06).
connected(static03, static08).
connected(static04, static07).
connected(static05, static06).
connected(static06, static09).
% connected(static07, static11).
% connected(static07, static12).
connected(static09, static10).

% connected(static01,Node).
%	Generates one of the following:
% 		connected(static01, static02).
% 		connected(static01, static03).
% 		connected(static01, static04).
connected(static01, Node) :-
	static01List(L),			% Initialise allowed nodes
	R is random(3),				% Pick a random number
	decide01(R, Node),			% Get node
	member(Node, L).			% Make sure it is allowed

% connected(static02,Node).
%	Generates one of the following:
% 		connected(static02, static05).
% 		connected(static02, static06).
connected(static02, Node) :-
	static02List(L),			% Initialise allowed nodes
	R is random(2),				% Pick a random number
	decide02(R, Node),			% Get node
	member(Node, L).			% Make sure it is allowed

% connected(static02,Node).
%	Generates one of the following:
% 		connected(static07, static11).
% 		connected(static07, static12).
connected(static07, Node) :-
	static07List(L),			% Initialise allowed nodes
	R is random(2),				% Pick a random number
	decide07(R, Node),			% Get node
	member(Node, L).			% Make sure it is allowed

% connected(N1, N2).
%	Dynamically connected nodes.
%	N1 is the first node
%	N2 is the second node
connected(N1, N2) :-
	static(SList),				% Initialise static node list
	not(member(N1, SList)),		% Make sure it is not a member
	R2 is random(200),			% Pick a random number
	node(N2, R2).				% Use identifier to get a node

% staticList(List).
% 	A list of static nodes that are not allowed 
%	to have a dynamic connection.
%	List is the list of nodes
static(List) :-
	List = [entrance, static01, static02, static03,
			static04, static06, static07, static09].

% static#List(L).
%	A list of static nodes that are connected to static#
%	# signifies first node
%		e.g. static01
%	L is the list of nodes
static01List(L) :- L = [static02, static03, static04].
static02List(L) :- L = [static05, static06].
static07List(L) :- L = [static11, static12].

% no_entry([List]).
%	A list of nodes that must not be entered
%	Only two nodes, a static and a random
no_entry([static11,RandomNode]) :-
	RandomID is random(199),
	node(RandomNode,RandomID).

% adjacent(Node1, Node2).
%	Node1, Node2 are two adjacent nodes.
adjacent(Node1, Node2) :-
	connected(Node1, Node2);
	connected(Node2, Node1).

% run_multi_adjacent(Node1,Node2).
%	Initialises multiple adjacent Start and End 
%	parameters. Creates one adjacent node by default
%	the multi_adjacent algorithm then creates more
%	adjacent nodes, depending on the End value
run_multi_adjacent(Node1, Node2) :-
	Start = 0,
	End is random(5),
	adjacent(Node1, Node2),
	multi_adjacent(Node1, Node3, Start, End).

% multi_adjacent(Node1,Node2,Start,End).
%	generates multiple adjacent nodes to the 
%	current node. The algorithm acts as a
%	makeshift for loop.
multi_adjacent(_, _, End, End) :- !.
multi_adjacent(Node1, Node2, Start, End) :-
	End > Start,
	NewStart is Start + 1,
	adjacent(Node1, Node2),
	multi_adjacent(Node1, Node3, NewStart, End).

% f(Node,Value).
%	Node is any node
%	Value is the estimated cost from Node to next node (g(n))
%	h(n) is considered 0, as it is a dynamic node
f(entrance,1).
f(Node, Old, Value) :-
	Value is Old + 1.
	
% goal(Node).
%	Goal of the search algorithm
goal(exit).

% --------------------------------------------------------------------
% End Maze Model
% --------------------------------------------------------------------


% --------------------------------------------------------------------
% Debugging Functions
% --------------------------------------------------------------------

% solve(Entry,Exit).
%	Debug function to see if nodes are dynamically created
%	Does not take into account the distance between nodes
%	Entry is the chosen entrance to the maze
%	Exit is the chosen exit for the maze
solve(Entry, Exit) :-
	NodesVisited = [Entry],
	path(Entry,Exit,NodesVisited).

% path(exit, exit, NodesVisited).
%	exit is the exit
%	NodesVisited is the list of nodes visited
path(exit, exit, NodesVisited) :-
	printlist(NodesVisited).
	
% path(Entry,Exit, NodesVisited).
%	Entry is the starting point of recursion
%	Exit is the goal node
%	NodesVisited is the list of nodes visited
path(Entry, Exit, NodesVisited) :-
	adjacent(Entry, NextNode),
	no_entry(No_nodes),
	not(member(NextNode, No_nodes)),
	path(NextNode,Exit,[NextNode|NodesVisited]).
% --------------------------------------------------------------------
% End Debugging Functions
% --------------------------------------------------------------------


% --------------------------------------------------------------------
% Helper Functions
% --------------------------------------------------------------------

% member(X, List).
%	X is a member of a list (from frequent.pl), a file
%	from the paper's repository
member(X, [X|_]).		% X is the head of the list
member(X, [_|Rest]) :-
	member(X, Rest).	% X is in the tail of the list
	
% printlist(List).
%	Prints any list
printlist([]).
printlist([Head|Tail]) :- 
	printlist(Tail),
	write(Head),
	write(' ').

% --------------------------------------------------------------------
% End Helper Functions
% --------------------------------------------------------------------

% --------------------------------------------------------------------
% Bratko's IDA* Algorithm
% --------------------------------------------------------------------
%	From paper repository

% Figure 12.10:  An implementation of the IDA* algorithm.


% idastar( Start, Solution):
%   Perform IDA* search; Start is the start node, Solution is solution path

idastar(Start, Solution)  :-
	retract(next_bound(_)), fail     % Clear next_bound
	;
	asserta(next_bound(0)),         % Initialise bound
	idastar0(Start, Solution).
  
idastar0(Start, Sol)  :-
	retract(next_bound(Bound)),      % Current bound
	asserta(next_bound(99999)),      % Initialise next bound
	f(Start, F),                     % f-value of start node
	df([Start], F, Bound, Sol)       % Find solution; if not, change bound
	;
	next_bound(NextBound),
	NextBound < 99999,               % Bound finite
	idastar0(Start, Sol).% Try with new bound

% df( Path, F, Bound, Sol):
%  Perform depth-first search within Bound
%  Path is the path from start node so far (in reverse order)
%  F is the f-value of the current node, i.e. the head of Path

df([N|Ns], F, Bound, [N|Ns])  :-
	F =< Bound,
	goal(N).                        % Succeed: solution found

df([N|Ns], F, Bound, Sol)  :-
	F =< Bound,                      % Node N within f-bound
	length(Ns, ListLength),
	ListLength < 100,
	no_entry(No_nodes),
	run_multi_adjacent(N, N1),
	not(member(N1, No_nodes)),
	f(N, F, F1),
	df([N1,N | Ns], F1, Bound, Sol).

df(_, F, Bound, _)  :-
	F > Bound,                       % Beyond Bound
	update_next_bound(F),           % Just update next bound
	fail.                            % and fail

update_next_bound(F)  :-
	next_bound(Bound),
	Bound =< F, !                      % Do not change next bound
	;
	retract(next_bound(Bound)), !,   % Lower next bound
	asserta(next_bound(F)).
% --------------------------------------------------------------------
% End Bratko's IDA* Algorithm
% --------------------------------------------------------------------
% ====================================================================